#include"Heap.h"

#include<malloc.h>
#include<string.h>
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void swap(HPDataType *left,HPDataType *right)
{
  HPDataType temp=*left;
  *left=*right;
  *right=temp;
}
// 向下调整
void AdjustDown(Heap* hp,int parent)
{
  int child=parent*2+1;
  int size=hp->size;
  while(child<size)
  {
    if(child+1<size && hp->a[child]<hp->a[child+1])
    {
      child+=1;
    }
    if(hp->a[parent]<hp->a[child])
    {
      swap(&hp->a[parent],&hp->a[child]);

      parent=child;
      child=parent*2+1;
    }
    else{
      return;
    }
  }
}
// 向上调整
void AdjustUp(Heap* hp)
{
  int child=hp->size-1;
  int parent=(child-1)/2;
  while(child>0)
  {
    if(hp->a[child]>hp->a[parent])
    {
      swap(&hp->a[child],&hp->a[parent]);

      child=parent;
      parent=(child-1)/2;
    }
    else{
      return;
    }
  }
}
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* arr, int n)
{
  hp->a=(HPDataType*)malloc(sizeof(HPDataType)*n);
  if(NULL==hp->a)
  {
    assert(0);
    return;
  }

  hp->capacity=n;
  hp->size=0;
  memcpy(hp->a,arr,sizeof(HPDataType)*n);

  hp->size=n;
  int root=(n-2)/2;
  for(;root>=0;root--)
  {
    AdjustDown(hp,root);
  }
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
  assert(hp);
  if(hp->a)
  {
    free(hp->a);
    hp->a=NULL;
    hp->capacity=0;
    hp->size=0;
  }
}
// 检查容量
static void CheckCapacity(Heap* hp)
{
  assert(hp);
  int newcapacity=hp->capacity*2;
  if(hp->size==hp->capacity)
  {
    int* temp=(HPDataType*)malloc(sizeof(HPDataType)*newcapacity);
    if(NULL==temp)
    {
      assert(0);
      return;
    }
    memcpy(temp,hp->a,sizeof(HPDataType)*(hp->size));

    free(hp->a);
    hp->a=temp;
    hp->capacity=newcapacity;
  }
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
  CheckCapacity(hp);

  hp->a[hp->size]=x;
  hp->size++;

  AdjustUp(hp);
}
// 堆的删除
void HeapPop(Heap* hp)
{
  assert(hp);
  if(HeapEmpty(hp))
  {
    return;
  }
  swap(&hp->a[hp->size-1],&hp->a[0]);
  hp->size-=1;

  AdjustDown(hp,0);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
  assert(!HeapEmpty(hp));
  return hp->a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
  assert(hp);
  return hp->size;
}

// 堆的判空
int HeapEmpty(Heap* hp)
{
  assert(hp);
  return 0==hp->size;
}

int Less(int left,int right)
{
  return left<right;
}

int Greater(int left,int right)
{
  return right>left;
}

// 测试函数
void TestHeap()
{
  Heap hp;
  int arr[]={2,23,4,5,6,67,87,28};
  int sz=sizeof(arr)/sizeof(arr[0]);
  HeapCreate(&hp,arr,sz);
  int i;
//  HeapPush(&hp,-1);
  for(i=0;i<hp.size;i++)
  {
    printf("%d ",hp.a[i]);
  }
  printf("\n");

  HeapDestory(&hp);
}
 // TopK问题：找出N个数里面最大/最小的前K个问题。
 // 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，
 // 需要注意：
 // 找最大的前K个，建立K个数的小堆
 // 找最小的前K个，建立K个数的大堆
void PrintTopK(Heap *hp,int* arr, int n, int k)
{
  hp->a=(HPDataType*)malloc(sizeof(HPDataType)*k);
  HeapCreate(hp,arr,k);
  int i=k;
  for(;i<n;i++)
  {
    if(arr[i]<hp->a[0])
    {
      hp->a[0]=arr[i];
      AdjustDown(hp,0);
    }
  }
  int j=0;
  for(;j<k;j++)
  {
    printf("%d ",hp->a[j]);
  }
  printf("\n");
}

void TestTopk()
{
  Heap hp;
  int n = 10000;
  int* a = (int*)malloc(sizeof(int)*n);
  srand(time(0));
  int i=0;
  for (; i < n; ++i)
  {
    a[i] = rand() % 1000000; 
  }
  a[5] = 1;
  a[1231] =  2;
  a[531] =  3;
  a[5121] =  4;
  a[115] =  5;
  a[2335] =  6;
  a[9999] =  7;
  a[76] =  8;
  a[423] =  9;
  a[3144] = 10;
  PrintTopK(&hp,a,n,10);
}
